// 访问结点 P，并将结点 P 入栈;
// 判断结点 P 的左孩子是否为空，
// 若为空，则取栈顶结点并进行出栈操作，
// 并将栈顶结点的右孩子置为当前的结点 P，循环至 1);
// 若不为空，则将 P 的左孩子置为当前的结点 P;
// 直到 P 为 NULL 并且栈为空，则遍历结束。
void PreOrder(BinTree* root) {
  stack<BinTree*> stkNode;
  BinTree* pNode = root;
  while (pNode || !stkNode.empty()) {
    while (pNode) {
      cout << pNode->data << ",";
      stkNode.push(pNode);
      pNode = pNode->leftChild;
    }
    if (!stkNode.empty()) {
      pNode = stkNode.top();
      stkNode.pop();
      pNode = pNode->rightChild;
    }
  }
}

//若其左孩子不为空，则将 P 入栈并将 P 的左孩子置为当前的 P， 然后对当前结点 P
//再进行相同的处理；
//若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，
//然后将当前的 P 置为栈顶结点的右孩子； 直到 P 为 NULL
//并且栈为空则遍历结束

void MidOrder(BinTree* root) {
  stack<BinTree*> stkNode;
  BinTree* pNode = root;
  while (pNode || !stkNode.empty()) {
    while (pNode) {
      stkNode.push(pNode);
      pNode = pNode->leftChild;
    }
    pNode = stkNode.top;
    stkNode.pop();
    pNode << pNode->data << ",";
    pNode = pNode->rightChild;
  }
}

// 在迷宫中进行深度优先搜索，搜索完成后栈中即为迷宫的一条可达路径
void searchPath(int[][] maze, int[] start, int[] end) {
  // 创建一个栈保存迷宫路径
  Stack<int[]> stack = new Stack<>();
  // 将迷宫入口位置压入栈中
  maze[start[0]][start[1]] = 2;
  stack.push(start);
  while (!stack.empty()) {
    int[] point = stack.peek();
    int x = point[0];
    int y = point[1];
    maze[x][y] = 2;  // 将基准节点标记为已搜索
    if (x == end[0] && y == end[1]) {
      printf("找到出口(%d,%d)\n", x, y);
      break;
    }
    // 向上下左右搜索
    if (maze[x + 1][y] == 0) {
      stack.push(new int[]{x + 1, y});
      continue;
    }
    if (maze[x - 1][y] == 0) {
      stack.push(new int[]{x - 1, y});
      continue;
    }
    if (maze[x][y - 1] == 0) {
      stack.push(new int[]{x, y - 1});
      continue;
    }
    if (maze[x][y + 1] == 0) {
      stack.push(new int[]{x, y + 1});
      continue;
    }
    // 上下左右都搜索不到活节点
    maze[x][y] = 3;  // 标记为死节点
    stack.pop();     // 从栈顶弹出
  }
}

// 逆序输出栈中的元素, 打印迷宫路径
void printStack(Stack<int[]> stack) {
  if (stack.size() > 0) {
    int[] point = stack.pop();
    printStack(stack);
    printf("(%d,%d)", point[0], point[1]);
  }
}
